class Solution {
public:
const int N=2000;
int mx(int a,int b){
    return a>b?a:b;
    }
    int longestCommonSubsequence(string s1, string s2) {
        // a[n] b[n]
            // a[i]==b[i]   common.append(a[i])
 int a[N][N];
    int len1 = s1.length();
    int len2 = s2.length();
    int i,j;
    
    memset(a,0,sizeof(int)*N*N);
    int max = 0;
    for(i=1; i<=len1; i++){
        for(j=1; j<=len2; j++){
            a[i][j] = mx(a[i-1][j],a[i][j-1]);
            if(s1[i-1]==s2[j-1]) {
                a[i][j] = mx(a[i][j], a[i-1][j-1]+1); 
                if(a[i][j] > max) max = a[i][j];
            }
        }
    }
    
    return max;
            
    }
};